package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.sun.org.apache.bcel.internal.generic.ReturnaddressType;



import com.sun.xml.internal.ws.addressing.model.MissingAddressingHeaderException;

import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.TraverseUtils;
import util.datastructure.ListNode;

/*
 * 
原题　
	Sort a linked list in O(n log n) time using constant space complexity.
题目大意
	使用恒定空间复杂度在O(n log n)时间内对链表进行排序。
解题思路
	O(n log n): 时间
	常量                  : 空间
			明显是归并排序啊！！！！
	
	知识点1：归并排序的整体思想
	知识点2：找到一个链表的中间节点的方法
	知识点3：合并两个已排好序的链表为一个新的有序链表
	
	参考：@_021_Merge_Two_Sorted_Lists	
	
   @Difficult Medium
 * @Date 2017-09-14 23:19
 */
public class _148_Sort_List {

	public void sortList() {
		
	}
	
    /**
     * 得到链表的中间节点
     * @return
     */
	public ListNode getMiddleListNode(ListNode head) {
		if (head==null || head.next==null)	return head;
		//两个指针,一个快(一次移动两格),一个慢(一次移动一格)
		ListNode fast = head, slow = head;
		while (fast.next!=null && fast.next.next != null) {
			fast = fast.next.next;
			slow = slow.next;
		}
		return slow;
	}
	
    public ListNode sortList(ListNode head) {
    	if (head==null || head.next==null) 	return  head;
    	ListNode lo = head;
    	ListNode mid = getMiddleListNode(head);
    	ListNode hi = mid.next;
    	mid.next = null;
        return merge(sortList(lo), sortList(hi));		//递归
    }	
	
	public ListNode merge(ListNode l1, ListNode l2) {
		ListNode dummpHead = new ListNode(-1);	//临时节点 
		ListNode tail = dummpHead;
		while (l1!=null && l2!=null) {
			if (l1.val < l2.val) {		
				tail.next = new ListNode(l1.val);					//取较小值
				l1 = l1.next;
			} else if (l1.val > l2.val) {
				tail.next = new ListNode(l2.val);					//取较小值
				l2 = l2.next;
			} else {
				tail.next = new ListNode(l1.val);					//都一样随便取个
				l1 = l1.next;
			}
			tail = tail.next;
		}
		tail.next = (l1==null) ? l2 : l1; 
		return dummpHead.next;
	}

	public static void main(String[] args) {
		_148_Sort_List obj = new _148_Sort_List();
		ListNode.traverse("sort list", obj.sortList(ListNode.newLinkListNotOrder()));
	}

}
